/*
题目：Morris遍历二叉树
https://leetcode.cn/problems/binary-tree-preorder-traversal/
https://leetcode.cn/problems/binary-tree-inorder-traversal/
 */
public class MorrisTraversal {
    //Morris前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        TreeNode cur = root;

        while (cur != null) {
            TreeNode curLeft = cur.left;
            if (curLeft != null) {
                //走到右子树的最后一个节点
                while (curLeft.right != null && curLeft.right != cur) {
                    curLeft = curLeft.right;
                }
                if (curLeft.right == null) {  //如果没有线索化
                    list.add(cur.val);
                    curLeft.right = cur;
                    cur = cur.left;
                } else {   //如果已经线索化了
                    cur = cur.right;
                    curLeft.right = null;
                }
            } else {  //如果左子树为空
                list.add(cur.val);
                cur = cur.right;
            }
        }

        return list;
    }

    //morris中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<> ();

        while (root != null) {
            TreeNode rootLeft = root.left;
            if (rootLeft != null) {  //如果左子树不为空
                while (rootLeft.right != null && rootLeft.right != root) {
                    rootLeft = rootLeft.right;
                }
                if (rootLeft.right == null) {  //如果还没线索化
                    rootLeft.right = root;
                    root = root.left;
                } else {  //如果已经线索化
                    list.add(root.val);
                    root = root.right;
                    rootLeft.right = null;
                }
            } else {   //如果左子树为空
                list.add(root.val);
                root = root.right;
            }
        }

        return list;
    }
}
